package ACWing.SearchAndGraphTheory.最短路;
//854. Floyd求最短路

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/31 22:11
 */
public class Floyd {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int k=sc.nextInt();
        int[][]dist=new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(i==j){
                    dist[i][j]=0;
                }else {
                    dist[i][j]=(int)1E9;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            dist[a][b]=Math.min(dist[a][b],c);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int l = 1; l <=n ; l++) {
                    dist[j][l]=Math.min(dist[j][l],dist[j][i]+dist[i][l]);
                }
            }
        }

        for (int i = 0; i < k; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            if(dist[a][b]<(int)1E9/2){
                System.out.println(dist[a][b]);
            }else {
                System.out.println("impossible");
            }
        }
    }
}
